/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * assignment1
 * Copyright (C)  2010 <>
 *
 * assignment1 is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * assignment1 is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef _S_F_GAME_H_
#define _S_F_GAME_H_

#include "s-f-game.h"
#include "game.h"
#include <string>
#include "circularlist.h"
#include "simplelist.h"
#include "utilityNode.h"
#include <boost/unordered_map.hpp>
#include <boost/array.hpp>
#include <fstream>

#include <boost/random/linear_congruential.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/generator_iterator.hpp>


#define MAX_SIZE 20
using namespace std;

typedef boost::unordered_map<std::string, double *> MyMap;
// This is a typedef for a random number generator.
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand base_generator_type;


class SFGame: public Game
{
	// Need to store strategies of players
	bool symmetric;

	// data read from GAMBIT input file
	int noofplayers;
	int *noofactions; // array hold no of actions per player
	double  *utilityMatrix; // holds the utilities of the players as listed in the input file.
	int numberofStrategyProfiles;

	// data structures
	circularlist **playerStrategyCircularLists;
	simplelist  <utilityNode> *payoffList;
	MyMap payoffMap;
	MyMap NEMap;

	// Strategy DataStructures - START
	bool **eliminatedStrategies;// player x strategy

	//for dominated strategies
	bool **strictlyDOMINATEDStrategies; // player x strategy
	bool **weaklyDOMINATEDStrategies_Type1; // player x strategy
	bool **weaklyDOMINATEDStrategies_Type2; // player x strategy
	int ***strictlyDOMINATEDCount; // player x strategy x strategy
	int ***weaklyDOMINATEDCount; // player x strategy x strategy

	//for dominant strategies
	bool **strictlyDOMINANTStrategies; // player x strategy
	bool **weaklyDOMINANTStrategies_Type1; // player x strategy
	bool **weaklyDOMINANTStrategies_Type2; // player x strategy
	int ***weaklyDOMINANTCount; // player x strategy x strategy
	int ***strictlyDOMINANTCount; // player x strategy x strategy

	bool ***undecided;// player x strategy x strategy
	bool **notDOMINANT; // player x strategy
	ofstream outputFile;
	ofstream finalResultsFile;

	// THIS IS A VERY IMPORTANT PARAMETER!!! THIS CONTROLS LOOPING DURING BEST RESPONSE DYNAMICS !
	// USED CRUCIALLY IN findNashEquilibriaByTabuSearch() method.
	// IF value = 3, then tabu was not able to detect cycles of length 4 when the game had 3 players with 3 players each
	// the above example was taken from Fudenberg and Tirole book on Game theory. Page 39. Fig 1.24.
	// one heuristic to set this value = length of longest possible cycle in the given game.
	// but not sure if it is the best idea or it prevents looping.
	// this indicates in a way the hardness of computing PSNE!!
	const static int TABU_TENURE = 100;
	boost::array<string, TABU_TENURE> tabuList;
	static int tabuCounter;
	// Strategy DataStructures - END
	static char DELIMITER;
	static double PSNE;
	static double SDSE;
	static double WDSE;
	static double IDSE;

	int *sampleCount;

	// very important parameter. it indicates how many rounds the tabu search algorithm needs to
	// run to find PSNE starting with a random seed in every iteration.
	//increasing this paramter can lead to discovering more NE as in this algorithm we are not doing
	// brute force search. HEnce we are not guaranteed to find all PSNE within the number of rounds configured.
	const static int NO_OF_ROUNDS = 500;

public:
	SFGame();
	~SFGame();
	int readGameFromFile();
	double to_double(std::string const& str);
//	void regexpTest(char *p);
	void solveForDominantStrategies();
//	void solveForIteratedDominantStrategies();
	void checkForDominantStrategies();
	// void checkForWeaklyDominantStrategies();
	int initializeDataStructures();
	void generateNextStrategyProfile(int **a);
	double getUtilityValue(int *stratProfile, int player);
	void generateNextStrategyProfile_ExceptPlayer_i(int **stratProfile, int excludedPlayer);
	void iteratedEliminationOfDominatedStrategies();
	void resetStrategyDataStructures();
	void resetplayerStrategyCircularLists();
	void resetEliminatedStrategies();

	void findNashEquilibriaByTabuSearch();
	void getRandomStrategyProfile(int *stratProfile);
	bool isStratProfileBestResponseForPlayer_i(int *stratProfile, int player);
	int getNextBestResponse(int *bestResponseList, int index1);
	void updateTabuArray(int *stratProfile);
	void resetTabuArray();
	void getBestResponseListInDecreasingOrder(int *bestResponseList, int *stratProfile, int player );
	bool IsStratProfileInTabuList(int *stratProfile);
	int getRandomNumberUsingBoostLibrary(int min, int max, int sampleCount, int player);

	void displayALLPSNE();

protected:

private:
	// void experiment(base_generator_type & generator);
	void logIterativeEliminationResults(ofstream& out, int& itCount);
	void logPSNEResults(ofstream& out, int *stratProfile);
	void logALLPSNE(ofstream& out);

};

#endif // _S_F_GAME_H_

